Defining the Node class

from typing import List

class Node:
    def __init__(self, value_ = 0, left_ = None, right_ = None):
        self.value = value_
        self.left = left_
        self.right = right_

Constructing Binary tree from in-order and pre-order traversal

Algorithm

1. Base Case – Empty Tree Check:

   • If both inOrder and preOrder are empty, return None.

2. Base Case – Single Node Tree:

   • If both lists have only one element:
     • Check if the elements are the same.
     • If yes, return a new Node with that value.
     • Else, raise an exception — traversals don’t match.

3. Identify Root:

   • The first element of the preOrder list is the root of the current (sub)tree.

4. Find Root in Inorder Traversal:

   • Locate the index of the root in inOrder.
   • All elements before this index belong to the left subtree.
   • All elements after this index belong to the right subtree.

5. Divide Traversals for Subtrees:

   • Slice inOrder:
     • leftTree_In = inOrder[0:rootIndex]
     • rightTree_In = inOrder[rootIndex+1:]
   • Use the size of the left subtree (len(leftTree_In)) to divide preOrder:
     • leftTree_Pre = preOrder[1:n], where n = len(leftTree_In) + 1
     • rightTree_Pre = preOrder[n:]

6. Recursive Construction:

   • Create a new Node with the root value.
   • Recursively construct the left subtree using leftTree_In and leftTree_Pre.
   • Recursively construct the right subtree using rightTree_In and rightTree_Pre.
   • Assign these to rootNode.left and rootNode.right.

7. Return Root:

   • Return the rootNode containing the entire subtree rooted at this node.

---

class InPreOrder():
    def createBinaryTree(self, inOrder: List[int], preOrder: List[int]) -> Node:
        if len(inOrder) == 0 and len(preOrder) == 0:
            return None
        
        # print("Preorder", end = ''); print(preOrder)
        # print("Inorder", end = ''); print(inOrder); print()
        
        if len(preOrder) == 1 and len(inOrder) == 1:
            if preOrder[0] == inOrder[0]:
                return Node(preOrder[0])
            raise Exception("There was some error")
        
        root = preOrder[0]
        rootIndex = inOrder.index(root)
        leftTree_In = inOrder[0: rootIndex]
        rightTree_In = inOrder[rootIndex + 1: len(inOrder)]
    
        n = len(leftTree_In) + 1
        leftTree_Pre = preOrder[1: n]
        rightTree_Pre = preOrder[n: len(preOrder)]
    
        # print(rightTree_In); print(rightTree_Pre)
    
        rootNode = Node(root)
        rootNode.left = self.createBinaryTree(leftTree_In, leftTree_Pre)
        rootNode.right = self.createBinaryTree(rightTree_In, rightTree_Pre)
    
        return rootNode

Constructing Binary tree from in-order and post-order traversal

Algorithm

1. Base Case – Empty Tree Check:

   • If both inOrder and postOrder are empty, return None.

2. Base Case – Single Node Tree:

   • If both lists have only one element:
     • Check if the elements are the same.
     • If yes, return a new Node with that value.
     • Else, raise an exception — traversals don’t match.

3. Identify Root:

   • The last element of the postOrder list is the root of the current (sub)tree.

4. Find Root in Inorder Traversal:

   • Locate the index of the root in inOrder.
   • All elements before this index belong to the left subtree.
   • All elements after this index belong to the right subtree.

5. Divide Traversals for Subtrees:

   • Slice inOrder:
     • leftTree_In = inOrder[0:rootIndex]
     • rightTree_In = inOrder[rootIndex+1:]
   • Use the size of the left subtree (n = len(leftTree_In)) to divide postOrder:
     • leftTree_Pre = postOrder[0:n]
     • rightTree_Pre = postOrder[n:len(postOrder)-1] (excluding last element which is root)

6. Recursive Construction:

   • Create a new Node with the root value.
   • Recursively construct the left subtree using leftTree_In and leftTree_Pre.
   • Recursively construct the right subtree using rightTree_In and rightTree_Pre.
   • Assign these to rootNode.left and rootNode.right.

7. Return Root:

   • Return the rootNode containing the entire subtree rooted at this node.

---

class InPostOrder:
    def createBinaryTree(self, inOrder: List[int], postOrder: List[int]) -> Node:
        if len(inOrder) == 0 and len(postOrder) == 0:
            return None
        
        # print("Preorder", end = ''); print(postOrder)
        # print("Inorder", end = ''); print(inOrder); print()
        
        if len(postOrder) == 1 and len(inOrder) == 1:
            if postOrder[0] == inOrder[0]:
                return Node(postOrder[0])
            raise Exception("There was some error")
        
        root = postOrder[-1]
        rootIndex = inOrder.index(root)
        leftTree_In = inOrder[0: rootIndex]
        rightTree_In = inOrder[rootIndex + 1: len(inOrder)]
    
        n = len(leftTree_In)
        leftTree_Pre = postOrder[0: n]
        rightTree_Pre = postOrder[n: len(postOrder) - 1]
    
        rootNode = Node(root)
        rootNode.left = self.createBinaryTree(leftTree_In, leftTree_Pre)
        rootNode.right = self.createBinaryTree(rightTree_In, rightTree_Pre)
    
        return rootNode

Function to traverse a binary tree

def traverse(tree):
    if not tree:
        return
    if tree.left or tree.right:
        print("\nRoot:", tree.value)
    else:
        print("\nLeaf:", tree.value)
    if tree.left:
        print("Left:", tree.left.value)
    if tree.right:
        print("Right:", tree.right.value)
    traverse(tree.left)
    traverse(tree.right)

Traversals

pre_order = [10, 20, 40, 50, 30, 60]
in_order = [40, 20, 50, 10, 60, 30]
post_order = [40, 50, 20, 60, 30, 10]

Driver code

tree1 = InPreOrder().createBinaryTree(in_order, pre_order)
traverse(tree1)

Root: 10
Left: 20
Right: 30

Root: 20
Left: 40
Right: 50

Leaf: 40

Leaf: 50

Root: 30
Left: 60

Leaf: 60

tree2 = InPostOrder().createBinaryTree(in_order, post_order)
traverse(tree2)

Root: 10
Left: 20
Right: 30

Root: 20
Left: 40
Right: 50

Leaf: 40

Leaf: 50

Root: 30
Left: 60

Leaf: 60

As we can see, both these trees are the same. This shows that our algorithm works.

---